package com.dynamicPlanning;

/**
 * 给定两个字符串str1和str2,输出两个字符串的最长公共子串
 * 题目保证str1和str2的最长公共子串存在且唯一。
 * 输入："1AB2345CD","12345EF"
 * 返回值： "2345"
 */
public class 最长公共子串 {
    public static void main(String[] args) {
        String str1 = "1AB2345CD"   , str2 = "12345EF";
        System.out.println(LCS1(str1,str2));

    }

    /**
     *暴力求解法
     */
    public static String LCS1 (String str1, String str2) {
        // write code here
        String maxSubStr = "";
        for (int i = 0; i < str1.length(); i++) {
            for (int j = i; j < str1.length()+1; j++) {
                if(str2.contains(str1.substring(i,j)) && j-i > maxSubStr.length()){
                    maxSubStr = str1.substring(i,j);
                }
            }
        }
        return maxSubStr;
    }

    /**
     *动态规划
     */
    public static String LCS2(String str1, String str2) {
        int maxLen = 0;
        int endIndex = 0;
        int[][] dp = new int[str1.length()+1][str2.length()+1];
        for (int i = 0; i < str1.length(); i++){
            for (int j = 0; j < str2.length(); j++) {
                if(str1.charAt(i) == str2.charAt(j)){
                    dp[i+1][j+1]=dp[i][j]+1;
                }
                if(dp[i+1][j+1] > maxLen){
                    maxLen = dp[i+1][j+1];
                    endIndex = i;
                }
            }
        }
        return str1.substring(endIndex - maxLen+1,endIndex+1);
    }

    public static String LCS3(String str1, String str2) {
        int maxLenth = 0;//记录最长公共子串的长度
        //记录最长公共子串最后一个元素在字符串str1中的位置
        int maxLastIndex = 0;
        int[] dp = new int[str2.length() + 1];
        for (int i = 0; i < str1.length(); i++) {
            //注意这里是倒叙
            for (int j = str2.length() - 1; j >= 0; j--) {
                //递推公式，两个字符相等的情况
                if (str1.charAt(i) == str2.charAt(j)) {
                    dp[j + 1] = dp[j] + 1;
                    //如果遇到了更长的子串，要更新，记录最长子串的长度，
                    //以及最长子串最后一个元素的位置
                    if (dp[j + 1] > maxLenth) {
                        maxLenth = dp[j + 1];
                        maxLastIndex = i;
                    }
                } else {
                    //递推公式，两个字符不相等的情况
                    dp[j + 1] = 0;
                }
            }
        }
        //最字符串进行截取，substring(a,b)中a和b分别表示截取的开始和结束位置
        return str1.substring(maxLastIndex - maxLenth + 1, maxLastIndex + 1);
    }
}
